package prac2;

import java.util.Random;

/**
 * Skeleton code for Prac 2. 
 *
 * @author     ram
 * @modified   Brendon Taylor (July 2010) - Formatting / Syntax errors
 * @modified   Brendon Taylor (August 2010) - 
 * @since      March 2006
 * @input      none
 * @output     none
 */
/*
 * Note to students: the Javadoc comments for this class use
 * nonstandard tags @pre, @post and @complexity, to document
 * preconditions, postconditions and complexity, respectively.  In
 * order for these tags to work, you will need to follow the
 * directions in the Javadoc guide which you will find under Week 1 of
 * the FIT1008 Moodle site.  If you do not want to use Javadoc, please
 * replace these tags with ordinary user-readable comments and add a
 * list of methods to the class comment above.
 */
public class Prac2 {
    public static final int ARRAY_SIZE = (int)Math.pow(2, 22) - 1;
    private static int[] randomArray=makeRandomArray(Integer.MIN_VALUE / 2, Integer.MAX_VALUE / 2, ARRAY_SIZE);
    
    /**
     * Creates and returns an array containing randomly-generated integers.
     * 
     * The integers are generated using java.util.Random.
     * 
     * @pre        from must be smaller than to, else the method 
     *             throws an IllegalArgumentException.
     * @pre        size is non-negative
     * @complexity O(size*Comp), where Comp is the complexity of 
     *             java.util.Random.nextInt() (probably O(1))
     * @param      from  the smallest number that can be generated
     * @param      to    upper bound to the numbers that can be generated 
     *                   (exclusive)
     * @param      size  the size of the array to create
     * @throws     IllegalArgumentException if to is not larger than from.
     * @return     an array of the requested size containing integers in 
     *             the range [from, to)
     */
    public static int[] makeRandomArray(int from, int to, int size) {
        Random rng = new Random();
        int[] newArray = new int[size];
        
        for (int i = 0; i < size; i++) {
             newArray[i] = rng.nextInt(to - from) + from;
        }
        return newArray;
            
    }
    
    
    /**
     * Return the sum of the first N elements in array
     * 
     * @pre        array exists
     * @pre        0< N <= array.length , else the method throws an ArrayIndexOutOfBoundsException
     * @post       the sum of the first N elements in array is returned
     * @complexity worst case: O(N)
     * @complexity best case: O(1), when array is empty
     * @param      array 
     * @param      N the first N element
     * @return     the sum of the first N elements in array
     */
    public static long sumElements(int[] array, int N){
    	long sum=0;
    	if(array.length==0){
    		return 0;
    	}
    	try {
    			for(int i =0;i<N;i++){
    				sum=sum+array[i];
    			}
    	}catch(ArrayIndexOutOfBoundsException e){
    		System.out.println("Array Index Out Of Bounds !!!");
    	}
    	return sum;
    }
    
    /**
     * Test the sumELements() method
     * 
     * @pre        method sumElements exists
     * @post       the sum of the first N elements of the testing arrays is printed     
     * @complexity worst case: O(N)based on the complexity of sumElements(), where N is the number of elements that need to be add up
     * @complexity base case:  O(1)based on the complexity of sumElements(), when array is empty 
     */
    public static void testSumElements(){
    	int[] arrayA = new int[] {};
    	int[] arrayB = new int[] {-3,-2,-1,0,1,2,3};
    	long sumOfArrayA=Prac2.sumElements(arrayA, 5);
    	long sumOfArrayB=Prac2.sumElements(arrayB, 4 );
    	System.out.println("sumOfArrayA is "+ sumOfArrayA);
    	System.out.println("sumOfArrayB is "+ sumOfArrayB);
    }
    
    /**
     * Return the running time of sumElments on array
     * 
     * @pre        array exists
     * @pre        0< N <= array.length , else the method throws an ArrayIndexOutOfBoundsException
     * @post       the running time of sumElements is returned 
     * @complexity worst case: O(N)based on the complexity of sumElements(), where N is the number of elements that need to be add up
     * @complexity base case:  O(1)based on the complexity of sumElements(), when array is empty 
     * @param      array
     * @param      N the first N element
     * @return     the running time of sumElments on array
     */
    public static long timeSumElements(int[] array, int N){
    	long timeBefore, timeAfter, timeTaken;
    	timeBefore = System.nanoTime();
    	Prac2.sumElements(array, N);
    	timeAfter = System.nanoTime();
    	timeTaken = timeAfter - timeBefore;
    	return timeTaken;
    	
    }
    
    /**
     * Uses the randomArray to call timeSumElements with different Ns and calculates the time needed
     * to add up the N contents of the array, and prints the time taken for this call
     * 
     * @pre        array exists
     * @pre        0< N <= array.length , else the method throws an ArrayIndexOutOfBoundsException
     * @complexity O(N)based on the complexity of sumElements(), where N is the number of elements that need to be add up
     * @param      array
     * @return     the running time of sumElments on array
     */
    public static void tableTimeSumElements(int[] array){
    	System.out.println("------N=1000,2000,3000,4000,5000---20000--------");
    	for( int N =1000; N<=20000; N=N+1000){
    		System.out.println(Prac2.timeSumElements(array, N));
    	}
    	System.out.println();
    	System.out.println("------N=10,100,1000,10000,100000,1000000--------");
    	for( int N =10; N<=1000000; N=N*10){
    		System.out.println(Prac2.timeSumElements(array, N));
    	}
    }
    
    /**
     * Return the sum of the elements at even indices whose position is less than N
     * @pre        array exists
     * @pre        0< N <= array.length+1 , else the method throws an ArrayIndexOutOfBoundsException
     * @complexity O(N) for worst case and O(1) when the array is empty
     * @param      array
     * @param      N
     */
    public static long  sumEvenElements(int[] array, int N) {
    	long sum=0;
    	if(array.length==0){
    		return 0;
    	}
    	try{
    		for(int i=0;i<N;i=i+2){
    			sum=sum+array[i];
    		}
    	}catch (ArrayIndexOutOfBoundsException e){
    		System.out.println("Array Index Out Of Bounds!!!");
    	}
    	return sum;
	}
    
    /**
     * Return the running time of sumEvenElments on array
     * 
     * @pre        array exists
     * @pre        0< N <= array.length+1 , else the method throws an ArrayIndexOutOfBoundsException
     * @post       the running time of sumEvenElements is returned 
     * @complexity worst case: O(N)based on the complexity of sumElements()
     * @complexity base case:  O(1)based on the complexity of sumElements(), when array is empty 
     * @param      array
     * @param      N
     * @return     the running time of sumElments on array
     */
    public static long timeSumEvenElements(int[] array, int N){
    	long timeBefore, timeAfter, timeTaken;
    	timeBefore = System.nanoTime();
    	Prac2.sumEvenElements(array, N);
    	timeAfter = System.nanoTime();
    	timeTaken = timeAfter - timeBefore;
    	return timeTaken;
    	
    }
    
    /**
     * Uses the randomArray to call timeSumEvenElements with different Ns and calculates the time needed
     * to add up the N contents of the array, and prints the time taken for this call
     * 
     * @pre        array exists
     * @pre        size is non-negative
     * @complexity O(N) for both best case and worst case
     * @param      array
     */
    public static void tableTimeSumEvenElements(int[] array){
    	System.out.println("------N=1000,2000,3000,4000,5000---20000--------");
    	for( int N =1000; N<=20000; N=N+1000){
    		System.out.println(Prac2.timeSumEvenElements(array, N));
    	}
    	System.out.println();
    	System.out.println("------N=10,100,1000,10000,100000,1000000--------");
    	for( int N =10; N<=1000000; N=N*10){
    		System.out.println(Prac2.timeSumEvenElements(array, N));
    	}
    }
    
    /**
     * Return the sum of the elements whose indices are less than N and powers of 2
     * @pre        array exists
     * @pre        size is non-negative
     * @complexity O(logN) for both best case and worst case
     * @param      array
     * @param      N
     */    
    public static long sumPowerElements(int[] array, int N){
    	long sum=array[1];
    	if(array.length<=1){
    		return 0;
    	}
    	for(int i=2;i<N;i=i*2){
    		sum=sum+array[i];
    	}
    	return sum;
    }
    
    /**
     * Return the running time of sumPowerElments on array
     * 
     * @pre        array exists
     * @pre        size is non-negative
     * @complexity O(logN), because the complexity of sumPowerElements is O(logN)
     * @param      array
     * @param      N
     * @return     the running time of sumPowerElments on array
     */
    public static long timeSumPowerElements(int[] array, int N){
    	long timeBefore, timeAfter, timeTaken;
    	timeBefore = System.nanoTime();
    	Prac2.sumPowerElements(array, N);
    	timeAfter = System.nanoTime();
    	timeTaken = timeAfter - timeBefore;
    	return timeTaken;
    	
    }
    
    /**
     * Uses the randomArray to call timePowerElements with different Ns and calculates the time needed
     * to add up the N contents of the array, and prints the time taken for this call
     * 
     * @pre        array exists
     * @pre        size is non-negative
     * @complexity O(logN) for both best case and worst case
     * @param      array
     */
    public static void tableTimeSumPowerElements(int[] array){
    	System.out.println("------N=1000,2000,3000,4000,5000---20000--------");
    	for( int N =1000; N<=20000; N=N+1000){
    		System.out.println(timeSumPowerElements(array, N));
    	}
    	System.out.println();
    	System.out.println("------N=10,100,1000,10000,100000,1000000--------");
    	for( int N =10; N<=1000000; N=N*10){
    		System.out.println(timeSumPowerElements(array, N));
    	}
    }
    
    /**
     * To sum elements in array, beginning at array[0] and ending as soon as a negative number is reached
     * or you have traversed the first N elements.
     * @pre        array exists
     * @pre        size is non-negative
     * @complexity best case O(1), worst case O(N)
     * @param      array
     * @param      N
     */
    public static long sumUntilNegative(int[] array, int N){
    	long sum=0;
    	int i=0;
    	if(array[0]<0 || array.length==0){
    		return 0;
    	}
    	while (array[i]>0 && i<N){
    		sum=sum+array[i];
    		i++;
    	}
    	return sum;
    }
    
    /**
     * Return the running time of sumUntilNegative on array
     * 
     * @pre        array exists
     * @pre        size is non-negative
     * @complexity Best case O(1), worst case O(N)
     * @param      array
     * @param      N
     * @return     the running time of sumUntilNegative on array
     */ 
    public static long timeSumUntilNegative1(int[] array, int N){
    	long timeBefore, timeAfter, timeTaken;
    	array[0]=4;
    	timeBefore = System.nanoTime();
    	Prac2.sumUntilNegative(array, N);
    	timeAfter = System.nanoTime();
    	timeTaken = timeAfter - timeBefore;
    	return timeTaken;
    	
    }
    
    /**
     * Return the running time of sumUntilNegative on array
     * 
     * @pre        array exists
     * @pre        size is non-negative
     * @complexity Best case O(1)
     * @param      array
     * @param      N
     * @return     the running time of sumUntilNegative on array
     */ 
    public static long timeSumUntilNegative2(int[] array, int N){
    	long timeBefore, timeAfter, timeTaken;
    	array[0]=-5;
    	timeBefore = System.nanoTime();
    	Prac2.sumUntilNegative(array, N);
    	timeAfter = System.nanoTime();
    	timeTaken = timeAfter - timeBefore;
    	return timeTaken;
    	
    }
    
    /**
     * Uses the randomArray to call timeSumUntilNagtive1 with different Ns and calculates the time needed
     * to add up the N contents of the array, and prints the time taken for this call
     * 
     * @pre        array exists
     * @pre        size is non-negative
     * @complexity best case O(1), worst case O(N)
     * @param      array
     */
    public static void tableTimeSumUntilNegative1(int[] array){
    	System.out.println("------N=1000,2000,3000,4000,5000---20000--------");
    	for( int N =1000; N<=20000; N=N+1000){
    		System.out.println(timeSumUntilNegative1(array, N));
    	}
    	System.out.println();
    	System.out.println("------N=10,100,1000,10000,100000,1000000--------");
    	for( int N =10; N<=1000000; N=N*10){
    		System.out.println(timeSumUntilNegative1(array, N));
    	}
    }
    
    /**
     * Uses the randomArray to call timeSumUntilNagtive2 with different Ns and calculates the time needed
     * to add up the N contents of the array, and prints the time taken for this call
     * 
     * @pre        array exists
     * @pre        size is non-negative
     * @complexity best case O(1), worst case O(N)
     * @param      array
     */
    public static void tableTimeSumUntilNegative2(int[] array){
    	System.out.println("------N=1000,2000,3000,4000,5000---20000--------");
    	for( int N =1000; N<=20000; N=N+1000){
    		System.out.println(timeSumUntilNegative2(array, N));
    	}
    	System.out.println();
    	System.out.println("------N=10,100,1000,10000,100000,1000000--------");
    	for( int N =10; N<=1000000; N=N*10){
    		System.out.println(timeSumUntilNegative2(array, N));
    	}
    }

    /**
     * To find the Max Sum Interval of the array
     * @pre        array exists
     * @pre        size is non-negative
     * @complexity O(N^3) for both best case and worst case
     * @param      array
     * @param      N
     */
    public static int[] findMaxSumInterval(int[] array, int N){
    	int iMin=0, min=0, max=0, iMax=0, iSum =0;
    	for(min=0; min<N; min++){
    		for(max=min+1;max<=N;max++){
    			int sum=0;
    			for(int i=min; i<=max;i++){
    				sum=sum+array[i];
    			}
    			if(sum>iSum){
    				iSum=sum;
    				iMin=min;
    				iMax=max;
    			}
    		}
    	}
    	System.out.println("iSum="+iSum);
    	return new int[] {iMin, iMax};
    }
    
    /**
     * Return the running time of findMaxSumInterval on array
     * 
     * @pre        array exists
     * @pre        size is non-negative
     * @complexity O(N^3) for both best case and worst case
     * @param      array
     * @param      N
     * @return     the running time of findMaxSumInterval on array
     */    
    public static long timeFindMaxSumInterval(int[] array, int N){
    	long timeBefore, timeAfter, timeTaken;
    	timeBefore = System.nanoTime();
    	Prac2.findMaxSumInterval(array, N);
    	timeAfter = System.nanoTime();
    	timeTaken = timeAfter - timeBefore;
    	return timeTaken;
    	
    }
    
    /**
     * Uses the randomArray to call findMaxSumInterval with different Ns and calculates the time needed
     * to add up the N contents of the array, and prints the time taken for this call
     * 
     * @pre        array exists
     * @pre        size is non-negative
     * @complexity O(N^3) for both best case and worst case
     * @param      array
     */
    public static void tableTimeFindMaxSumInterval(int[] array){
    	System.out.println("------N=1000,2000,3000,4000,5000---20000--------");
    	for(int N = 1000; N <= 20000; N += 1000){
    		System.out.println(Prac2.timeFindMaxSumInterval(array, N));
    	}
    	System.out.println();
    	System.out.println("------N=10,100,1000,10000,100000,1000000--------");
    	for(int N = 10; N <= 1000000; N *= 10){
    		System.out.println(Prac2.timeFindMaxSumInterval(array, N));
    
    	}
    }
    
    /**
     * To determine whether there is a subset of array elements that add up to exactly the target.
     * 
     * @pre        array exist
     * @complexity O(2^N), where N is the length of array
     * @param      array
     * @param      target
     * @return     return true if such a subset exists, otherwise return false
     */
    public static boolean subsetSum(int[] array, int target){
    	int i=0;
    	boolean[] subset = new boolean[array.length + 1];
    	do{
    		long sum = 0;
    		for(int j=0; j<array.length;j++){
    			if(subset[j]){
    				sum=sum+array[j];
    			}
    		}
    		if(sum==target){
    			return true;
    		}
    		for (i=0; i<array.length && subset[i]; i++){
    			subset[i]=false;
    		}
    		subset[i] = true;
    	} while (!subset[array.length]);
    	return false;
    }
    
    /**
     * Return the running time of findMaxSumInterval on array
     * 
     * @pre        array exists
     * @pre        size is non-negative
     * @complexity O(N^2) for both best case and worst case
     * @param      array
     * @param      N
     * @return     the running time of findMaxSumInterval on array
     */    
    public static long timeSubsetSum(int[] array, int target){
    	long timeBefore, timeAfter, timeTaken;
    	timeBefore = System.nanoTime();
    	Prac2.subsetSum(array, target);
    	timeAfter = System.nanoTime();
    	timeTaken = timeAfter - timeBefore;
    	return timeTaken;
    	
    }
    
//    /**
//     * Uses the randomArray to call findMaxSumInterval with different Ns and calculates the time needed
//     * to add up the N contents of the array, and prints the time taken for this call
//     * 
//     * @pre        array exists
//     * @pre        size is non-negative
//     * @complexity O(N^2) for both best case and worst case
//     * @param      array
//     */
//    public static void tableTimeSubsetSum(int[] array){
//    	System.out.println("------N=1000,2000,3000,4000,5000---20000--------");
//    	for(int N = 1000; N <= 20000; N += 1000){
//    		System.out.println(Prac2.timeFindMaxSumInterval(array, N));
//    	}
//    	System.out.println();
//    	System.out.println("------N=10,100,1000,10000,100000,1000000--------");
//    	for(int N = 10; N <= 1000000; N *= 10){
//    		System.out.println(Prac2.timeFindMaxSumInterval(array, N));
//    
//    	}
//    }
    
    /**
     * @param args Command-line arguments
     */
    public static void main(String[] args) {
        randomArray =  makeRandomArray(Integer.MIN_VALUE / 2, Integer.MAX_VALUE / 2, ARRAY_SIZE);
        // test sumElements()
        testSumElements();
        
        System.out.println("Sum Elements");
        tableTimeSumElements(randomArray);
        System.out.println();
        
        System.out.println("Sum Even Elements");
        tableTimeSumEvenElements(randomArray);
        System.out.println();
        
        System.out.println("Sum Power Elements");
        tableTimeSumPowerElements(randomArray);
        System.out.println();
        
        System.out.println("Sum Until Negative 1");
        tableTimeSumUntilNegative1(randomArray);
        System.out.println();
             
        System.out.println("Sum Until Negative 2");
        tableTimeSumUntilNegative2(randomArray);
        System.out.println();
        
        int[] newArray = new int[] {3,4,10,-5,20,2,7};
        System.out.println("The result of subsetSum() is "+Prac2.subsetSum(newArray, 24));
        
        System.out.println("FindMax Sum Interval");
        tableTimeFindMaxSumInterval(randomArray);
        System.out.println();
        
    }
}